package com.algorithms.techniques;

import java.util.Arrays;
import java.util.Random;

public class QuickSort {

	int[] arrayToBeSorted=null;
	public QuickSort(int[] iArrayToBeSorted)
	{
		arrayToBeSorted=Arrays.copyOf(iArrayToBeSorted, iArrayToBeSorted.length);
		quicksort(0,iArrayToBeSorted.length-1);
	}
	
	public void quicksort(int p,int r)
	{
		if(p<r)
		{		
			int partition = randomPartition( p, r);
			quicksort(p,partition-1);
			quicksort(partition+1,r);
		}
	}
	private int randomPartition(int p,int r)
	{
		Random rand = new Random();	
		int num=p+rand.nextInt(r-p);
		System.out.println("Random="+num);
		swap(num,r);
		return partition(p,r);
	}
	private int partition(int p,int r)
	{
		int pivot =arrayToBeSorted[r];
		int i=p-1;
		for(int j=p;j<r ;j++)
		{
			if(arrayToBeSorted[j] <pivot)
			{
				i=i+1;
				swap(i,j);
			}
		}
		swap(i+1,r);
		return i+1;
		
	}
	
	private void swap(int pos1,int pos2)
	{
		int temp=arrayToBeSorted[pos1];
		arrayToBeSorted[pos1]=arrayToBeSorted[pos2];
		arrayToBeSorted[pos2]=temp;
	}
	public int[] getSortedArray()
	{
		for(int a:arrayToBeSorted)
		{
			System.out.println(a);
		}
		return arrayToBeSorted;
	}
	
}
